package 二叉树;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
 */
public class _107_二叉树的层序遍历II {
    Queue<TreeNode> queue = new LinkedList<>();
    LinkedList<List<Integer>> list = new LinkedList<>();
    List<Integer> subList = new ArrayList<>();

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        int levelSize = 1;
        if (root == null) return list;
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            subList.add(node.val);
            levelSize--;
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
            if (levelSize == 0){
                //链表的头插法  最后插入的先输出
                list.addFirst(subList);
                subList = new ArrayList<>();
                levelSize = queue.size();
            }
        }

        return list;

    }
}
